﻿using System;

namespace AlgorithmPractice;

/// <summary>
/// 直接插入排序
/// </summary>
public class StraightInsertionSort
{
    public static void Sort(int[] toBeSorted)
    {
        StartSort(toBeSorted);
        Console.WriteLine(string.Join("、", toBeSorted));
    }

    /// <summary>
    /// 直接插入排序是把新的数据插入以及排序好的数列中，
    /// 排序的基本方法是：每一步将一个待排序的元素，按其排序码的大小，插入到前面已经排好序的一组元素的适当位置上去，直到元素全部插入为止。
    /// 1. 从序列第一个元素开始，该元素可以认为已经被排序
    /// 2. 取出下一个元素，设为待插入元素，在已经排序的元素序列中从后向前扫描，如果该元素（已排序）大于待插入元素，将该元素移到下一位置。
    /// 3. 重复步骤2，直到找到已排序的元素小于或者等于待排序元素的位置，插入元素
    /// 4. 重复2，3步骤，完成排序。
    /// </summary>
    /// <param name="toBeSorted"></param>
    private static void StartSort(int[] toBeSorted)
    {
        int i, j;
        for (i = 1; i < toBeSorted.Length; i++)
        {
            var temp = toBeSorted[i];
            for (j = i - 1; j >= 0 && toBeSorted[j] > temp; j--)
            {
                toBeSorted[j + 1] = toBeSorted[j];
            }

            toBeSorted[j + 1] = temp;
        }
    }
}